/*
 *https://leetcode.cn/problems/capacity-to-ship-packages-within-d-days/
 *1011. 在 D 天内送达包裹的能力
 *medium 吴朝泽 2024.9.14
 *二分查找
check 函数用于验证是否可以在 d 天内完成运送所有货物，船的最大载重为 x。
如果当前天的载重加上当前货物的重量超过了 x ， 则需要增加一天，并且重新开始计算当前天的载重。
如果天数超过了允许的最大天数直接返回 false ，两个 if 都不执行的话就直接继续在当前天添加货物。
调用 check 函数判断是否能找到理想的值，l 从数组的最大元素位置开始， r 为数组元素之和 ，
如果可以找到则尝试更小的载重，如果不行则更改为更大的载重
*/


class Solution {
public:
    bool check(vector<int>& weights, int d, int x) 
    {
        int count = 1;        //从第一天开始
        int currentLoad = 0;  //当前天的载重
        for (int weight : weights) 
        {
            if (currentLoad + weight > x) 
            {
                count++;  
                currentLoad = weight;  
                if (count > d)  return false;  
            } 
            else 
                currentLoad += weight;            
        }
        return true;  
    }

    int shipWithinDays(vector<int>& weights, int days) {
        int l = *max_element(weights.begin(), weights.end());
        int r = accumulate(weights.begin(), weights.end(), 0);
        
        while (l < r) 
        {
            int mid = l + (r - l) / 2;             
            if (check(weights, days, mid))   r = mid;  
            else     l = mid + 1;                 
        }
        return l;  
    }
};
